With the increasing use and complexity of global networks for commercial and public purposes, link-state routing algorithms, being the main-stream of routing protocols today, grow more and more complex. One of the examples therefore is the P-NNI (ATM Forum, PNNI Specification Ver. 1.0, 1996), incorporated by reference herein, routing protocol specified by the ATM Forum body. Link-state routing protocols relied to transport topology information so far mostly on fixed-format packets that could be processed in an inexpensive manner. With the upcoming requirement of future extensibility of such protocols type-length-value (TLV) encoded packets are evolving. Parsing of such packets becomes very expensive. This invention presents a novel approach to process such packets in an incremental, fast way.
Networking of computers introduced several problems such as naming, addressing and routing (J. Schoch, Inter-network naming, addressing and routing. In IEEE Proc. Compcon, 1978) and naturally different solutions thereof. Recently, the focus in routing is shifting towards dynamic or state-adaptive routing (G. Ash, J. Chen, A. Frey, B. Huang, C. Lee, G. McDonald. Real-time network routing in the AT&T network-improved service quality at lower cost. In Globecom. AT&T Bell Laboratories, 1992; R. Callon, R. Guerin, E. Hoffman, J. Jeffords, G. Swallow. P-NNI routing hierarchy; overview and examples. P-NNI Working Group, March 1994). Such a routing does, beside saving a lot of configuration work, respond quickly to changes of available resources in the network and link failures. Moreover, this kind of routing becomes more and more of a necessity when introducing B-ISDN network technologies such as ATM (Jean-Yves Le Boudec, The Asynchronous Transfer Mode: A Tutorial. Computer Networks and ISDN Systems, 1992) that start to blur the boundary between carrier networks and privately operated computer networks.
Several design solutions exist for dynamic routing in computer networks and are still under development, distance vector (L. Ford and D. Fulkerson, Flows in Networks. Princeton University Press, 1962) and link-state (J. M. McQuillan, I. Richer, E. C. Rosen, ARPANET routing algorithms improvements. BBN Technical Report 3803, April 1978) oriented being the well-known ones. Due to its advantages in context of routing with quality of service requirements, link-state protocols are used as basics for emerging technologies such as ATM. The basic idea of link state routing protocols is that each node sends local topology information to its neighbors (R. Perlman, "Interconnections", Addison-Wesley, 1992, ISBN 0-201-56322-0). This information is propagated then using sophisticated `flooding` mechanisms through the network. As the result of such a process, every node in the network contains a view of the whole network topology in the so called "Topology Database". Newer link-state routing protocols incorporate a concept of `hierarchy`, where parts of the network collapse into a logical node in the view of distant nodes. The generation and flooding of information is repeated each time a node sees a significant change in available local resources. The distributed pieces of topology information, so called link state up-dates (LSU) or link state elements, carry a unique identifier and a version number increasing when the information inside of such an LSU is up-dated. Additionally, to prevent this process from being triggered too often, a dampening function controls the thresholds holding back non-significant changes. The topology database resulting from the execution of the `flooding` mechanism between nodes is used to compute routes that are requested by users then to reach desired destinations. Such routes are used e.g. in forwarding of packets or routing of call setups in connection-oriented networks.
Modern routing protocols, such as PNNI, following the trend towards extensibility for future requirements, abandon more and more fixed packet formats and start to use TLV (type-length-value) encoded packet schemes. The type describes the fixed part of the TLV transmitted and the length indicates the offset in the packet where the next TLV starts. In case where the length exceeds the length of the fixed part of the TLV, embedded TLVs are present. Generally, TLV encoded packets transferring topology information in modern routing protocols can be interpreted as representations of lists of arbitrary elements embedded in lists recursively. This approach, albeit very flexible, presents increased processing load in terms of CPU required. FIG. 1a visualizes two TLVs, first of them embedding two other TLVs.
The solution presented introduces a novel algorithm that allows to process changes to linked lists of arbitrary elements, possibly nested recursively, in an incremental manner. TLV encoded packets transferring topology information in modern routing protocols can be interpreted as representations of such structures. Because topology packets more often include changes in the content of list elements than changes to the list structure itself, it becomes less and less convenient to abandon the processed version of the previous list and fully process the structure of the new version. An incremental update algorithm introduced here, recognizing the changes in the contents of elements without unnecessarily deleting old elements, improves the performance of the protocol significantly.